1. Scope of the Invention
The present invention relates to computer calculation of an object's path through space which does not collide with other objects.
2. Related Prior Art
When designing products using computer aided techniques, it can be important to know whether the resulting product can be assembled and maintained easily. Since it is expensive and slow to build physical mock ups, there are significant advantages to simulating these physical systems and automatically determining if parts can be removed as expected. The problem of generating a path that does not cause the moving object to touch any other components has been call the "find path" problem described in T. Lozano-Perez and M. A. Wesley, "An Algorithm For Planning Collision-Free Paths Among Polyhedral Objects" Comm. of the ACM 22(10):560-570, October 1979.
Unfortunately, automatically generating paths is a non-trivial problem especially for trajectories with close tolerances or systems with many degrees of freedom. Testing for collisions between the moving object and structures in the workspace can be computationally expensive, and searching multi-dimensional spaces requires many collision checks.
The work space defines the space in which the moving object and the structures interact and the state space of the system represents all the possible states the moving object can obtain in the workspace. Although the work space of the system usually has only three dimensions, state space of the moving object can have six dimensions or more. For example, in a three dimensional work space a rigid moving part has six degrees of freedom: three to position the center of the object, and three to determine its orientation around its midpoint. Objects with joints or actuators, such as robotic arms, can have even more degrees of freedom.
A randomized path planner (RPP) method, as described in J. Barraquand, B. Langlois and J. C. Latombe, "Numerical Potential Field Techniques For Robot Path Planning" IEEE Transactions on Systems, Man, and Cybernetics, 22(2):224-241, 1992 has been a successful algorithm in solving find path problems. Its defines a state-space energy function which guides the moving object from the start to the end state using gradient descent.
RPP generates a state-space energy function by first creating a work-space energy function which can guide a point from the starting position to the ending position in the workspace. One or more guide points are chosen on the moving object to define the state-space function in terms of the work-space function. For any state of the moving object the state-space function is simply a weighted sum of the work-space function evaluated at the these guide points.
Unfortunately, the state-space function has local minima which trap the gradient descent algorithm before the moving object reaches the end state. In this situation RPP uses a random walk to escape the local minimum. This random walk is the bottle neck of the algorithm which spends most of its time escaping local minima.
A road map planner (RMP), described in L. Kavraki, "Randomized Preprocessing of Configuration Space for Fast Path Planning" IEEE Intl. Conf on Robotics and Automation, 1994, has recently been proposed as a successor to the RPP algorithm. It maps free space by testing individual states and the links which connect these states. The result is a net work, compared to highway system, which lies entirely inside of valid state space. The problem is then reduced to finding a path from the starting position to the network, and from the network to the goal.
Theoretically, this algorithm has advantages over RPP, but has not performed well in some test cases where local connections (or links) between two states are computationally expensive to establish. An interesting fact is that 80% of the search time was spent verifying a continuous connection of links throughout the network. Verifying continuity of the links is a computationally-expensive operation because a large number of collision checks may need to be performed along the link.
Currently there is a need for a system which efficiently calculates an automated path of a known object through space without colliding with other known objects.